package com.datastructure.test.longestpalindromesubseq;

public class LongestPalindromeSubSeq {

    public static void main(String[] args) {

    }

    public int longestPalindromeSubSeq (String s) {
        // write code here
        int length = s.length();
        StringBuilder stringBuilder = new StringBuilder(s);
        String reverseString = stringBuilder.reverse().toString();
        int[][] temp = new int[length+1][length+1];
        byte[] bytes = s.getBytes();
        byte[] reverseStringBytes = reverseString.getBytes();
        for (int i = 1; i <= bytes.length; i++) {
            for (int j = 1; j <= reverseStringBytes.length; j++) {
                if(bytes[i-1]==reverseStringBytes[j-1]){
                    temp[i][j]=temp[i-1][j-1]+1;
                } else {
                    temp[i][j]=Math.max(temp[i][j-1],temp[i-1][j]);
                }
            }
        }
        return temp[length][length];
    }

}
